package leetcode7;

import java.util.HashSet;

public class test24 {
    /*
    * 142. 环形链表 II*/
    //哈希表
    public ListNode detectCycle(ListNode head) {
        ListNode ptr = head;
        ListNode res = head;
        Set<ListNode> set = new HashSet<>();
        while(true){
            if(ptr == null) return null;
            if(set.contains(ptr)){
                res = ptr;
                break;
            }
            set.add(ptr);
            ptr = ptr.next;
        }
        return res;
    }
    //快慢指针
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head ,slow = head;
        while(true){
            if(fast == null || fast.next == null ) return null;

            fast = fast.next.next;
            slow = slow.next;


            if(fast == slow){
                fast = head;
                break;
            }
        }
        while(slow != fast){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}
